/// https://leetcode-cn.com/problems/3sum/
pub struct Solution;

impl Solution {
    pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        let n = nums.len();
        let mut v: Vec<Vec<i32>> = Vec::new();

        if n < 3 {
            return v;
        }

        // let mut nums = nums.to_owned();
        nums.sort();

        if nums.iter().take(3).sum::<i32>() > 0 || nums.iter().rev().take(3).sum::<i32>() < 0 {
            return v;
        }

        let mut sum: i32;
        let mut left: usize;
        let mut right: usize;

        for i in 0..n - 2 {
            if i > 0 && nums[i] == nums[i - 1] {
                continue;
            }
            if nums[i..i + 3].iter().sum::<i32>() > 0 {
                break;
            }
            if nums[i] + nums[n - 2..].iter().sum::<i32>() < 0 {
                continue;
            }

            left = i + 1;
            right = n - 1;
            while right > left {
                sum = nums[left] + nums[right] + nums[i];
                if sum == 0 {
                    v.push(vec![nums[i], nums[left], nums[right]]);
                    while right > left && nums[left] == nums[left + 1] {
                        left += 1;
                    }
                    while right > left && nums[right] == nums[right - 1] {
                        right -= 1;
                    }
                    right -= 1;
                    left += 1;
                } else if sum > 0 {
                    right -= 1;
                } else {
                    left += 1;
                }
            }
        }
        v
    }

    pub fn use_hashmap(nums: Vec<i32>) -> Vec<Vec<i32>> {
        use std::collections::HashMap;

        let n = nums.len();
        let mut v: Vec<Vec<i32>> = Vec::new();

        if n < 3 {
            return v;
        }

        let mut nums = nums.to_owned();
        nums.sort();

        if *nums.first().unwrap() > 0 {
            return v;
        }

        let mut hashmap: HashMap<i32, usize> = HashMap::new();
        for (i, num) in nums.iter().rev().enumerate() {
            hashmap.entry(*num).or_insert(n - 1 - i);
        }

        for i in 0..n - 2 {
            if i > 0 && nums[i] == nums[i - 1] {
                continue;
            }

            for j in i + 1..n - 1 {
                if j > i + 1 && nums[j] == nums[j - 1] {
                    continue;
                }

                if let Some(&pos) = hashmap.get(&-(nums[i] + nums[j])) {
                    if pos > j {
                        v.push(vec![nums[i], nums[j], nums[pos]])
                    } else {
                        break;
                    }
                }
            }
        }
        v
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn assert<F>(f: F)
        where F: Fn(Vec<i32>) -> Vec<Vec<i32>> {
        let nums = vec![-1, 0, 1, 2, -1, -4];
        // let res = f(nums);
        // assert!(res.contains(&vec![-1, -1, 2]) || res.contains(&vec![-1, 0, 1]));
        assert_eq!(f(nums), vec![vec![-1, -1, 2], vec![-1, 0, 1]]);

        let nums = vec![0, 0, 0];
        assert_eq!(f(nums), vec![vec![0, 0, 0]]);

        let nums = vec![-2, 0, 1, 1, 2];
        // let res = f(nums);
        // assert!(res.contains(&vec![-2, 0, 2]) || res.contains(&vec![-2, 1, 1]));
        assert_eq!(f(nums), vec![vec![-2, 0, 2], vec![-2, 1, 1]]);

        let nums = vec![];
        let v: Vec<Vec<i32>> = vec![];
        assert_eq!(f(nums), v);
    }

    bench!(assert Solution::use_hashmap);
    bench!(assert Solution::three_sum);
}
